package tld.test.interpreter
{
	/**
	 * This is a very basic LR(k) parser (hand-made).
	 * Grammar:
	 * Quote := /'/ Expression
	 * Expression := Atom | (Atom List)
	 * Atom := /[^\s]+/ | String
	 * List := Atom | Atom List | e
	 * Comment := /;/ /.*$/
	 * String := /"/ StringBody /"/
	 * StringBody := /[^"]+/ | /\/"/ StringBody | e
	 * 
	 * Literals or regular expressions are restricted 
	 * by "/" characters.
	 * 
	 * e is the emtpy character.
	 * 
	 * Quotes aren't implemented yet.
	 */
	public class Parser
	{
		private var _tail:String;
		
		/**
		 * Creates new parser.
		 */
		public function Parser() { super(); }
		
		/**
		 * Reads entire program text.
		 * 
		 * @param input The program body.
		 * 
		 * @return An array of s-expressions parsed from 
		 * the program text 
		 */
		public function read(input:String):Array
		{
			var result:Array = [];
			this._tail = input;
			while (this._tail)
				result.push(this.readExpression(this._tail));
			return result;
		}
		
		/**
		 * Reads single symbolic expression.
		 * 
		 * @param input Program text.
		 * 
		 * @return An expression constructed from the first 
		 * lexical element.
		 */
		public function readExpression(input:String):Expression
		{
			this._tail = input;
			return this.readToParen(input);
		}
		
		/**
		 * Returns the program text that was not parsed yet.
		 * 
		 * @return The part of the program that has not been red yet.
		 */
		public function tail():String
		{
			return this._tail;
		}
		
		// TODO: canRead and readToParen look much alike
		// can optimize later.
		public function canRead(text:String):Boolean
		{
			var result:Boolean = Boolean(text);
			var head:String;
			
			this._tail = text;
			if (result)
			{
				switch (text.charAt())
				{
					case ";":
						this._tail = this._tail.substr(
							Math.min(uint(this._tail.indexOf("\r")),
								uint(this._tail.indexOf("\n")), 
								this._tail.length));
						return this.canRead(this._tail);
					case "'":
						this._tail = this._tail.substr(1);
						if (this._tail.charAt() == "(")
							// this is an array (list)
							this.readUntilClose(this._tail);
							// untested
						else this.readSymbol(this._tail);
						break;
					case "(":
						head = this.readSymbol(text.substr(1));
						if (this._tail.charAt() != ")")
						{
							while (this._tail.charAt() != ")")
							{
								if (!this._tail) 
								{
									result = false;
									break;
								}
								if (!(result = this.canRead(this._tail)))
									break;
							}
							if (result && this._tail.charAt() == ")")
								this._tail = this._tail.substr(1);
						}
						else this._tail = this._tail.substr(1);
						break;
					case "\"":
						try
						{
							this.readString(text);
							result = true;
						}
						catch (error:String)
						{
							if (error == "Unterminated string")
								result = false;
							else throw error;
						}
						break;
					case " ":
					case "\r":
					case "\n":
					case "\t":
						if (text)
						{
							this._tail = text.substr(1);
							result = this.canRead(this._tail);
						}
						break;
					case ")":
						this._tail = this._tail.substr(1);
						break;
					default:
						if (text.length)
							this.readUntilWhite(text);
				}
			}
			return result;
		}
		
		private function readToParen(input:String):Expression
		{
			var head:String;
			var args:Array;
			var result:Expression;
			
			switch (input.charAt())
			{
				case ";":
					this._tail = this._tail.substr(
						Math.min(uint(this._tail.indexOf("\r")),
						uint(this._tail.indexOf("\n")), 
							this._tail.length));
					return this.readToParen(this._tail);
				case "\"":
					result = new Expression(this.readString(this._tail));
					break;
				case "'":
					trace("we hit tick");
					this._tail = this._tail.substr(1);
					if (this._tail.charAt() == "(")
					{
						// this is an array (list)
						result = new Expression("'" + 
							this.readUntilClose(this._tail));
					}
					// untested
					else result = 
						new Expression("'" + this.readSymbol(this._tail));
					break;
				case " ":
				case "\t":
				case "\r":
				case "\n":
					if (input.length)
					{
						this._tail = input.substr(1);
						result = this.readToParen(this._tail);
					}
					break;
				case ")":
					this._tail = this._tail.substr(1);
					result = null;
					break;
				case "(":
					head = this.readSymbol(input.substr(1));
					if (this._tail.charAt() != ")")
					{
						args = [];
						while (this._tail.charAt() != ")")
						{
							trace("reading arguments", this._tail);
							if (!this._tail) 
								throw "Syntax error: missing closing paren";
							args.push(this.readToParen(this._tail));
						}
						if (this._tail.charAt() == ")")
							this._tail = this._tail.substr(1);
					}
					else this._tail = this._tail.substr(1);
					result = new Expression(head, args);
					break;
				default:
					if (input.length)
						result = new Expression(
							this.readUntilWhite(input));
			}
			return result;
		}
		
		private function readString(input:String):String
		{
			var escaped:Boolean;
			var current:String;
			var i:int;
			var len:int = input.length;
			var ended:Boolean;
			trace("readString", input);
			while (i++ < len)
			{
				current = input.charAt(i);
				if (current == "\\") escaped = !escaped;
				else if (current == "\"" && !escaped)
				{
					ended = true;
					break;
				}
				else escaped = false;
			}
			if (!ended) throw "Unterminated string";
			this._tail = input.substr(i + 1);
			trace("readString tail", this._tail);
			return input.substr(0, i + 1);
		}
		
		private function readSymbol(input:String):String
		{
			var first:String = input.charAt();
			// probably not
			if (first == "(" || first == "'")
				return first + this.readUntilClose(input.substr(1));
			else return this.readUntilWhite(input);
		}
		
		private function readUntilWhite(input:String):String
		{
			var i:int;
			var whites:String = " \t\r\n)";
			var inputLength:int = input.length;
			
			while (whites.indexOf(input.charAt(i)) < 0 && 
				i < inputLength)
				i++;
			this._tail = input.substr(i);
			return input.substr(0, i);
		}
		
		private function readUntilClose(input:String):String
		{
			var i:int;
			var insideString:Boolean;
			var opens:int;
			var closed:int;
			var current:String;
			var escaped:Boolean;
			var finished:Boolean;
			
			trace("readUntilClose", input);
			while (i < input.length)
			{
				current = input.charAt(i);
				if (current == "\"" && !escaped)
				{
					insideString = !insideString;
					escaped = false;
				}
				else if (current == "\\" && insideString)
					escaped = !escaped;
				else if (!insideString)
				{
					if (current == "(") opens++;
					else if (current == ")") closed++;
					else if (current == ";")
					{
						input = input.substr(0, i - 1) + 
							input.substr(input.indexOf("\r"), i);
					}
					escaped = false;
				}
				i++;
				// first character must be the open paren
				if (closed == opens)
				{
					finished = true;
					break;
				}
			}
			this._tail = input.substr(i);
			trace("tail after readUntilClose", this._tail);
			return input.substr(0, i);
		}
	}
}